import java.sql.SQLOutput;
import java.util.*;

 class Node {
	int val;
	Node next;
	Node random;

	public Node(int val) {
		this.val = val;
		this.next = null;
		this.random = null;
	}
}
class solution{
	public List<String> topKFrequent(String[] words, int k) {



		//1、统计每个单词出现的次数
		Map<String,Integer> map = new HashMap<>();
		for (String word : words) {
			if(map.get(word) == null) {
				map.put(word,1);
			}else {
				int val = map.get(word);
				map.put(word,val+1);
			}
		}


		//2、建立小根堆,指定比较的方式
		PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>
				(new Comparator<Map.Entry<String, Integer>>() {
					@Override
					public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {

						if(o1.getValue().compareTo(o2.getValue()) == 0) {
							//按照字母顺序建立大根堆
							return o2.getKey().compareTo(o1.getKey());
						}

						return o1.getValue()-o2.getValue();
					}
				});
		//3、遍历map 调整优先级队列
		for(Map.Entry<String,Integer> entry: map.entrySet()) {
			if(minHeap.size() < k) {
				minHeap.offer(entry);
			}else {
				Map.Entry<String,Integer> top = minHeap.peek();
				//如果当前频率相同
				if(top.getValue().compareTo(entry.getValue()) == 0) {
					// 字母顺序小的进来
					if(top.getKey().compareTo(entry.getKey()) > 0) {
						//出队
						minHeap.poll();
						minHeap.offer(entry);
					}
				}else {
					if(top.getValue().compareTo(entry.getValue()) < 0) {
						minHeap.poll();
						minHeap.offer(entry);
					}
				}
			}
		}
		List<String> ret = new ArrayList<>();
		for (int i = 0; i < k; i++) {
			Map.Entry<String,Integer> top  = minHeap.poll();
			ret.add(top.getKey());
		}
		Collections.reverse(ret);
		return ret;
	}
}

class Solution {
	public int numJewelsInStones(String jewels, String stones) {
		Set<Character> set=new TreeSet<>();
		for (char ch:jewels.toCharArray()
			 ) {
			set.add(ch);
		}
		int count=0;
		for (char ch:stones.toCharArray()
			 ) {
			if(set.contains(ch)) {
				count++;
			}
		}
		return count;
	}
}
public class MapSet {
	public static void main2(String[] args) {
		Set<String> set=new TreeSet<>();
		Set<String> set1=new TreeSet<>();
		set1.add("hello1");
		set1.add("word1");

		set.add("word");
		set.add("hello");
		set.add("welcome");
		set.add("heihei");
		System.out.println(set.size());
		System.out.println(set);
		System.out.println(set.contains("hello"));
		System.out.println(set.contains("heiheiee"));
		System.out.println("========================");
		System.out.println(set.containsAll(set1));
		System.out.println(set.addAll(set1));
		System.out.println(set);
		System.out.println(set.isEmpty());
		String [] array=new String[10];
		set.toArray(array);
		System.out.println(Arrays.toString(array));
	}
	public static void main(String[] args) {
		Map<String,String> map=new TreeMap<>();
		map.put("林冲","豹子头");
		map.put("林冲", "豹子头");
		map.put("鲁智深", "花和尚");
		map.put("武松", "行者");
		map.put("宋江", "及时雨");
		map.put("李逵", "黑旋风");
		System.out.println(map.size());
		System.out.println(map);
		System.out.println(map.get("林冲"));//返回的是对应的value值
		// put(key,value): 注意key不能为空，但是value可以为空

		System.out.println(map.getOrDefault("林冲", "九纹龙"));
		//如果存在林冲，就会返回value，不存在返回默认值

		//在map中寻找是否这个key
		System.out.println(map.containsKey("linchong"));
		System.out.println(map.containsValue("豹子头"));

		//keySet是将map中key返回到set中，然后再进行遍历的
		for (String str1:map.keySet()
			 ) {
			System.out.print(str1+" ");
		}
		for (String s:map.values()
			 ) {
			System.out.print(s+" ");
		}
		//用一个集合来进行接受。
		Collection<String> collection=map.values();
		for( String s:collection) {
			System.out.println(s+" ");
		}
		for (Map.Entry<String,String> entry:map.entrySet()) {
			System.out.print(entry.getKey()+"  "+entry.getValue());
		}
	}

	public static void main3(String[] args) {
		Map<Integer,Integer> map=new HashMap<>();
		int [] nums={1,2,3,4,1,2,1,1};
		for (int i = 0; i < nums.length; i++) {
			if(map.get(nums[i])==null) {
				map.put(nums[i],1);
			} else {
				int val=map.get(nums[i]);
				map.put(nums[i],val+1);
			}
		}
	}

	public static void main4(String[] args) {
		int [] nums={1,1,1,1,2,2,3};
		Map<Integer,Integer> map=new HashMap<>();
		for(int i =0;i<nums.length;i++) {
			if(map.get(nums[i])==null) {
				map.put(nums[i],1);
			} else {
				int val=map.get(nums[i]);
				map.put(nums[i],val+1);
			}
		}
		int size=0;
		int count=0;
		int k=0;
		for(Map.Entry<Integer,Integer> entry:map.entrySet()) {
			if(entry.getValue()>2) {
				count+=2;
				size=2;
			} else {
				count+=entry.getValue();
				size=entry.getValue();
			}
			while(size>0&&k<count) {
				nums[k++]=entry.getKey();
				size--;
			}
		}
		Arrays.sort(nums,0,5);
	}
	public static void main1(String[] args) {
		for(int i =1;i<=9;i++) {
			for(int j=1;j<=i;j++) {
				System.out.print(i+"*"+j+"="+i*j+"\t");
			}
			System.out.println();
		}
	}
}
